#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
    
class Solution {
    public:
        string multiply(string num1, string num2) {
            int size1 = num1.size(), size2 = num2.size();
            vector<int> a1(size1, 0);
            vector<int> a2(size2, 0);
            vector<int> ans(size1+size2, 0);
            string str;
            for (int i = 0; i < size1; i++)
                a1[i] = num1[i] - '0';
            reverse(a1.begin(), a1.end());
            for (int i = 0; i < size2; i++)
                a2[i] = num2[i] - '0';
            reverse(a2.begin(), a2.end());
            for (int i = 0; i < size2; i++)  {
                int carry = 0;
                int b = a2[i];
                int j;
                for (j = 0; j < size1; j++) {
                    int a = a1[j];
                    int result = a*b + carry;
                    int sum =  ans[i+j] + result;
                    if (sum > 9) {carry = sum/10; sum -= carry*10;}
                    else carry = 0;
                    ans[i+j] = sum;
                }
                if (carry != 0)
                    ans[i+j] = carry;
                for (int k = 0; k < ans.size(); k++)
                    cout << ans[k] << " ";
                cout << endl;
            }
            bool start = true;
            for (int i = ans.size()-1; i >= 0; i--) {
                if (start && ans[i] != 0)
                    start = false;
                if (!start) {
                    char ch = ans[i] + '0';
                    str = str + ch;
                }
            }
            return str.size() == 0 ? "0" : str;
        }
};

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    string result;

    cout << "-----------------Test 1--------------------" << endl;
    result = mySolution.multiply("123","456");
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
